#include<iostream>
#include<assert.h>
#include<stdlib.h>

using std::cin;
using std::cout;
using std::endl;

namespace lly
{
  template<class T>
  struct QNode
  {
    T _x;
    QNode<T>* _next;
  };

  template<class T>
  class Queue 
  {
  public:
    Queue()
      :head(NULL)
      ,end(NULL)
    {}
    ~Queue()
    {
      QNode<T>* tmp = head;
      while(tmp != NULL)
      {
        QNode<T>* temp = tmp;
        tmp = tmp->_next;
        delete temp;
      }
      head = end = NULL;
    }

    void push(const T& x)
    {
      QNode<T>* tmp = new QNode<T>;
      tmp->_x = x;
      tmp->_next = NULL;
      if (head == NULL)
        head = end = tmp;
      else 
      {
        end->_next = tmp;
        end = tmp;
      }
    }

    const T& top()
    {
      assert(head != NULL);
      return head->_x;
    }

    void pop()
    {
      assert(head != NULL);
      if (head == end)
      {
        delete head;
        head = end = NULL;
      }
      else 
      {
        QNode<T>* tmp = head->_next;
        delete head;
        head = tmp;
      }
    }

    bool empty()
    {
      return end == NULL;
    }

  private:
    QNode<T>* head;
    QNode<T>* end;
  };
}
